
/**
 * 接雨水
 * LeetCode 42
 */

public class test3 {

    // 非双指针的方法：
//    public int trap(int[] height) {
//
//    }

    // 双指针法
    // 时间复杂度：O（n） 空间复杂度：O（1）
    public int trap2(int[] height) {
        int l = 1,r=height.length-2,lmax=height[0],rmax=height[height.length-1];
        int ans = 0;
        while(l <= r){
            if(lmax <= rmax){
                ans += Math.max(0,lmax - height[l]);
                lmax = Math.max(lmax,height[l++]);
            }else{
                ans += Math.max(0,rmax - height[r]);
                rmax = Math.max(rmax,height[r--]);
            }
        }
        return ans;
    }

}
